/*!
 * \file pbmaxclique.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Branch and bound algorithm for maximum clique with selective coloring.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <sys/resource.h>

#include <bitmap.h>
#include <graph.h>
#include <grinput.h>
#include <heurSelColoring.h>
#include <mcr.h>

typedef struct {
	Node node;
	BitMap * R;
	BitMap * S;
	int lb;
} Subproblem;

static int (*coloring)(BitMap *, int);

static int (*sortVertices)(Graph *, int *);

void pb_maxClique(Graph * g, int maxdeg, long long * nsubps, long long * memsz) {
	int n = g->n;

	Subproblem stack[++maxdeg];
	Subproblem * subp = stack;
	*memsz = maxdeg * sizeof(Subproblem);

	BitMap * vec = newBitMapVector(maxdeg << 1, n);
//	*memsz += (maxdeg << 1) * nnodes * WSIZE;

	int i;
	for (i = 0; i < (maxdeg << 1); i++, subp++) {
		subp->R = vec + i++;
		subp->S = vec + i;
	}

	subp = stack;
	addAllElements(subp->R);
	addAllElements(subp->S);

	initHeur(g);

	//initialize with a maximal clique
	if (g->maxcq < 0)
		g->maxcq = maxClique(subp->R);

	//build an initial coloring
	subp->lb = g->maxcq;
	mcsColoring_f(subp->S, subp->lb);

	(*nsubps) = 1;

	int topC = 0;
	rearWhile(subp->S, &subp->node);
	while (topC >= 0) {
		//get the next vertex in the candidate set
		prev(&subp->node);
		if (head(&subp->node)) {
			if (topC > g->maxcq)
				g->maxcq = topC;
			subp--;
			topC--;
			if (topC >= 0 && subp->lb < g->maxcq - topC) {
				coloring(subp->S, g->maxcq - topC - subp->lb);
				subp->lb = g->maxcq - topC;
			}
		} else {
			topC++;

			//Calculate the new candidate vector
			delElement(subp->R, &subp->node);

			Subproblem * newsubp = subp + 1;
			intersectOf(newsubp->R, neig(g, getElement(&subp->node)), subp->R);
			copyAll(newsubp->S, newsubp->R);

			//Build a coloring for the candidate's vector
			newsubp->lb = g->maxcq - topC;
			if (newsubp->lb <= 0)
				newsubp->lb = 0;
			else
				coloring(newsubp->S, newsubp->lb);
			(*nsubps)++;
			subp = newsubp;
			rearWhile(subp->S, &subp->node);
		}
	}

	*memsz += getMemSize();
	freeBitMap(stack->R);

	closeHeur();
}

int main(int argc, char *argv[]) {
	char name[200];
	FILE* graphFile = NULL;
	FILE* outFile = NULL;

	outFile = fopen(argv[1], "a+");
	graphFile = fopen(argv[2], "r");
	strcpy(name, argv[2]);
	int algo;
	if (argc >= 4)
		algo = atoi(argv[3]);
	else
		algo = 1;

	switch (algo) {
	case 1: {
		coloring = greedyColoring;
		break;
	}
	case 2: {
		coloring = mcsColoring;
		break;
	}
	case 3: {
		printf("Not implemented.\n");
		exit(0);
		break;
	}
	}

	int order;
	if (argc >= 5)
		order = atoi(argv[4]);
	else
		order = 1;

	switch (order) {
	case 1: {
		sortVertices = heapMcr;
		break;
	}
	case 2: {
		sortVertices = listMcr;
		break;
	}
	case 3: {
		sortVertices = decExdegree;
		break;
	}
	case 4: {
		sortVertices = decDegree;
		break;
	}
	}

	Graph * g = readDimacsGraph(graphFile);

	struct timeval tvoi, tvoe;
	float renumberTime;

	int maxdeg;
	gettimeofday(&tvoi, NULL);
	int R[g->n];
	maxdeg = sortVertices(g, R);

	Graph * gg = newRenumbered(g, R);
	gettimeofday(&tvoe, NULL);

	printf("maxdeg=%d\n",maxdeg);
	fflush(NULL);

	renumberTime = (tvoe.tv_sec - tvoi.tv_sec) + (tvoe.tv_usec - tvoi.tv_usec) / 1000000000.0;
	delGraph(g);
	free(g);

	gg->maxcq = -1;
	if (argc >= 6)
	{
		char * fnm = strstr(argv[2], "random/");
		if (fnm != NULL)
		{
			fnm = strchr(fnm, '/')+1;
		}
		else
		{
			fnm = strrchr(argv[2], '/');
			if (fnm == NULL)
				fnm = argv[2];
			else
				fnm = fnm + 1;
		}
		fnm = strtok(fnm, ".");

		FILE * maxFile = fopen(argv[5], "r");
		char linestr[100];
		char * solfilename;
		while (!feof(maxFile) && gg->maxcq < 0)
		{
			if (fgets(linestr, 100, maxFile) == NULL)
				break;
			solfilename = strtok(linestr, " ");
			int maxcq = atoi(strtok(NULL, " "));
			printf("%s %s\n", fnm, solfilename);
			fflush(NULL);
			if (!strcmp(fnm, solfilename))
			{
				gg->maxcq = maxcq;
				printf("%s %d\n", solfilename, gg->maxcq);
				fflush(NULL);
			}
		}
		fclose(maxFile);
	}

	long long memsz;
	long long ndolls;

	struct timespec start, end;
	struct timeval tvs, tve;
	float optimizationTime;

	gettimeofday(&tvs, NULL);
	pb_maxClique(gg, maxdeg, &ndolls, &memsz);
	gettimeofday(&tve, NULL);
	start.tv_sec = tvs.tv_sec;
	start.tv_nsec = tvs.tv_usec * 1000;
	end.tv_sec = tve.tv_sec;
	end.tv_nsec = tve.tv_usec * 1000;
	optimizationTime = (end.tv_sec - start.tv_sec);
	optimizationTime += (end.tv_nsec - start.tv_nsec) / 1000000000.0;

	printf(
			"%s \t n=%d  colorHeur=%d  sortVert=%d  sol=%d  initTime=%f  ndolls=%lld  time=%f  mem=%fKB  graphmem=%fKB \n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);
	fprintf(outFile,
			"%s \t %d \t %d \t %d \t %d \t %f \t %lld \t %f \t %f \t %f\n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);

	delGraph(gg);
	free(gg);
	fclose(outFile);
	fclose(graphFile);
	return 0;
}
